0148. 排序链表【中等】
1. 📝 题目描述
给你链表的头结点 head,请将其按 升序 排列并返回 排序后的链表。
示例 1:

txt
输入:head = [4,2,1,3]
输出:[1,2,3,4]1
2
2
示例 2:

txt
输入:head = [-1,5,3,4,0]
输出:[-1,0,3,4,5]1
2
2
示例 3:
txt
输入:head = []
输出:[]1
2
2
提示:
- 链表中节点的数目在范围
[0, 5 * 10^4]内 -10^5 <= Node.val <= 10^5
进阶:你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?
2. 🎯 s.1 - 归并排序
c
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* merge(struct ListNode* l, struct ListNode* r) {
struct ListNode dummy;
struct ListNode* cur = &dummy;
while (l && r) {
if (l->val <= r->val) {
cur->next = l;
l = l->next;
} else {
cur->next = r;
r = r->next;
}
cur = cur->next;
}
cur->next = l ? l : r;
return dummy.next;
}
struct ListNode* sortList(struct ListNode* head) {
if (!head || !head->next) return head;
struct ListNode* slow = head;
struct ListNode* fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
struct ListNode* mid = slow->next;
slow->next = NULL;
struct ListNode* left = sortList(head);
struct ListNode* right = sortList(mid);
return merge(left, right);
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
js
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var sortList = function (head) {
if (!head || !head.next) return head
// 找中点并断开
let slow = head,
fast = head.next
while (fast && fast.next) {
slow = slow.next
fast = fast.next.next
}
const mid = slow.next
slow.next = null
// 递归排序左右两半
const left = sortList(head)
const right = sortList(mid)
// 合并两个有序链表
const dummy = new ListNode(0)
let cur = dummy,
l = left,
r = right
while (l && r) {
if (l.val <= r.val) {
cur.next = l
l = l.next
} else {
cur.next = r
r = r.next
}
cur = cur.next
}
cur.next = l || r
return dummy.next
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
py
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
# 找中点并断开
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next
slow.next = None
left = self.sortList(head)
right = self.sortList(mid)
# 合并
dummy = ListNode(0)
cur = dummy
while left and right:
if left.val <= right.val:
cur.next = left
left = left.next
else:
cur.next = right
right = right.next
cur = cur.next
cur.next = left or right
return dummy.next1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
- 时间复杂度:
,其中 是链表的长度 - 空间复杂度:
,递归调用栈的深度
算法思路:
- 用快慢指针找到链表中点,将链表断开为两半
- 递归对左右两半分别排序
- 将两个有序链表合并为一个有序链表